public class O68 {
    TreeNode re;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root,p,q);
        return re;
    }
    boolean dfs(TreeNode root, TreeNode p, TreeNode q){
        if (root==null||re!=null)
            return false;
        boolean l = dfs(root.left, p, q);
        boolean r = dfs(root.right, p, q);
        if ((l&&r||((root==p)||(root==q))&&(l||r)))
            re = root;
        return l||r||root==p||root==q;
    }
}
